package com.shangxia.leetcode.hoot100.easy;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @ProjectName: leetcode
 * @ClassName: MajorityElement169
 * @Time: 2020/12/2
 * @Author: zhouy
 * @Description:
 * @Experience:
 */

@Slf4j
public class MajorityElement169 {
    public static void main(String[] args) {

    }

    /**
     * 哈希表
     *
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {
        if (ObjectUtils.isEmpty(nums)) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>(nums.length / 2);
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, 1 + map.get(num));
                if (map.get(num) >= (nums.length / 2)) {
                    return num;
                }
            } else {
                map.put(num, 1);
            }
        }
        int num = 0;
        int count = 0;
        for (Integer integer : map.keySet()) {
            if (map.get(integer) > count) {
                num = integer;
                count = map.get(integer);
            }
        }
        return num;
    }

    /**
     * 排序
     *
     * @param nums
     * @return
     */
    public static int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }


    /**
     * Boyer-Moore 投票算法
     *
     * @param nums
     * @return
     */
    public static int majorityElement3(int[] nums) {
        int majority = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                majority = nums[i];
            }
            if (majority == nums[i]) {
                count++;
            } else {
                count--;
            }
        }
        return majority;
    }

    /**
     * 去等数
     *
     * @param nums
     * @return
     */
    public static int majorityElement4(int[] nums) {
        int ans=nums[0],len=1;
        for(int i=1;i<nums.length;i++){
            //如果相等，就累计数量
            if(nums[i] == ans){
                len++;
            }else{
                //如果不等，就碰撞吧
                if(len>0)len--;
                else{
                    //当计数为零时，把下一个数暂时作为目标数
                    ans=nums[i];
                    len=1;
                }
            }
        }
        return ans;
    }

}
